Echo cancellers improve the voice quality in a voice communication by removing the echo from the voice communication. Such an echo canceller is exemplified in FIG. 1. x(t) is the speaker signal, y(t) is the microphone signal, s(t) is the echo from the speakers, v(t) is the near-end signal and H(z) represents adaptive filters.
Echo cancellers are based on estimating a model of the echo signal, usually implemented as an FIR (Finite Impulse Response) filter. Due to the time variations in the echo path, the model needs to be continuously adapted.
A Kalman filter is an example of a FIR filter which can be used for implementing the linear filter adaptation. The Kalman filter is given by
            h      ⁡              (                  t          +          1                )              =                  h        ⁡                  (          t          )                    +                        K          ⁡                      (            t            )                          ·                  (                                    y              ⁡                              (                t                )                                      -                                                            X                  T                                ⁡                                  (                  t                  )                                            ⁢                              h                ⁡                                  (                  t                  )                                                              )                                K      ⁡              (        t        )              =                            P          ⁡                      (            t            )                          ⁢                  X          ⁡                      (            t            )                                                            R            2                    ⁡                      (            t            )                          +                                            X              T                        ⁡                          (              t              )                                ⁢                      P            ⁡                          (              t              )                                ⁢                      X            ⁡                          (              t              )                                                      P      ⁡              (                  t          +          1                )              =                  P        ⁡                  (          t          )                    +                        R          1                ⁡                  (          t          )                    -                        K          ⁡                      (            t            )                          ⁢                              X            T                    ⁡                      (            t            )                          ⁢                  P          ⁡                      (            t            )                              
The computation of the updating gain in the Kalman filter includes the covariance matrix P(t) that has a dimension equal to the filter order. Hence, the computational load of the Kalman filter is in many situations prohibitively large for real-time implementation of echo cancellation.
Several approximations of the Kalman filter have been proposed to reduce the computational load and in particular the Normalized Least Mean Squares method for updating FIR filters with adaptive step-size computations can be viewed as an approximate Kalman filter implementation.
For speech signals, it is advantageous to implement the NLMS in the frequency domain, particularly for high sample rates. In order to handle long impulse responses, a partitioned block structure where the impulse response of the echo path is segmented into np consecutive blocks of length P coefficients is used,
                    H        echo            ⁡              (        z        )              =                            ∑                      n            =            0                                              (                                                n                  P                                -                1                            )                        ·            P                          ⁢                                  ⁢                              h            n                    ·                      z                          -              n                                          =                        ∑                      p            =            1                                n            P                          ⁢                                  ⁢                              ∑                          n              =              0                                      P              -              1                                ⁢                                          ⁢                                    h                              p                ,                n                                      ·                          z                                                                    -                                          (                                              p                        -                        1                                            )                                                        ·                  P                                -                n                                                                                      H          p                ⁡                  (          f          )                    =              FFT        ⁡                  (                      [                                                                                h                                          p                      ,                      0                                                                                                                    M                                                                                                  h                                          p                      ,                                              P                        -                        1                                                                                                                                                              0                                          M                      -                      P                                                                                            ]                    )                      ,                  ⁢          p      =      1        ,    K    ,          n      P                                    X          p                ⁡                  (                      k            ,            f                    )                    =              FFT        ⁡                  (                      [                                                                                x                    ⁡                                          (                                                                        k                          ·                          L                                                -                                                                              (                                                          p                              -                              1                                                        )                                                    ·                          P                                                -                        M                        +                        1                                            )                                                                                                                    M                                                                                                  x                    ⁡                                          (                                                                        k                          ·                          L                                                -                                                                              (                                                          p                              -                              1                                                        )                                                    ·                          P                                                                    )                                                                                            ]                    )                      ,                  ⁢          p      =      1        ,    K    ,          n      P                  S      ⁡              (        f        )              =                  ∑                  p          =          1                          n          P                    ⁢                          ⁢                                    H            p                    ⁡                      (            f            )                          ·                              X            p                    ⁡                      (            f            )                                          (              [                                            ρ                                                                          0                                  M                  -                  L                                                                                                        s                ⁡                                  (                                                            k                      ·                      L                                        -                    1                                    )                                                                                        M                                                                          s                ⁡                                  (                                      k                    ·                    L                                    )                                                                    ]            )        =          IFFT      ⁡              (                  S          ⁡                      (            f            )                          )            where x(t) is the loudspeaker signal, s(t) is the echo, L is the data frame length, and M is the FFT length.
Each partition is recursively estimated as
                    ⁢                                        H            p                    ⁡                      (                          k              ,              f                        )                          =                                            H              p                        ⁡                          (                                                k                  -                  1                                ,                f                            )                                +                                    α              ⁡                              (                                  k                  ,                  f                                )                                      ·                          (                                                E                  ⁡                                      (                                          k                      ,                      f                                        )                                                  ·                                                      X                    p                    *                                    ⁡                                      (                                          k                      ,                      f                                        )                                                              )                                          ,                          ⁢                          ⁢              p        =        1            ,      K      ,              n        P                                ⁢    where              E      ⁡              (                  k          ,          f                )              =                  FFT        ⁡                  (                      [                                                            ρ                                                                                                  0                                          M                      -                      L                                                                                                                                        e                    ⁡                                          (                                                                        k                          ·                          L                                                -                        1                                            )                                                                                                                    M                                                                                                  e                    ⁡                                          (                                              k                        ·                        L                                            )                                                                                            ]                    )                    =                        FFT          ⁡                      (                          [                                                                    ρ                                                                                                              0                                              M                        -                        L                                                                                                                                                        y                      ⁡                                              (                                                                              k                            ·                            L                                                    -                          1                                                )                                                                                                                                  M                                                                                                              y                      ⁡                                              (                                                  k                          ·                          L                                                )                                                                                                        ]                        )                          -                  FFT          ⁡                      (                          [                                                                    ρ                                                                                                              0                                              M                        -                        L                                                                                                                                                        s                      ⁡                                              (                                                                              k                            ·                            L                                                    -                          1                                                )                                                                                                                                  M                                                                                                              s                      ⁡                                              (                                                  k                          ·                          L                                                )                                                                                                        ]                        )                              where y(t) is the microphone signal and α(k, f) is the update gain factor.
From an analysis of the expected variance of the estimation error of the filter coefficients, i.e. |Hm(k, f)−H0(k, f)|2 where H0 (k, f) denotes the filter coefficients of a linear filter modeling the echo, an adaptive updating gain that minimizes the expected estimation error may be implemented by choosing α(k, f) as κ(k, f) updated by
            κ      ⁡              (                  k          ,          f                )              =                            R          H                ⁡                  (                                    k              -              1                        ,            f                    )                                                  n            P                    ⁢                                    P              M                        ·                                          R                X                            ⁡                              (                                  k                  ,                  f                                )                                      ·                                          R                H                            ⁡                              (                                                      k                    -                    1                                    ,                  f                                )                                                    +                              n            P                    ⁢                      P            L                    ⁢                                    R              V                        ⁡                          (                              k                ,                f                            )                                                              R        H            ⁡              (                  k          ,          f                )              =                            (                      1            -                                          L                M                            ·                              κ                ⁡                                  (                                      k                    ,                    f                                    )                                            ·                                                R                  X                                ⁡                                  (                                      k                    ,                    f                                    )                                                              )                ·                              R            H                    ⁡                      (                          k              -              1                        )                              +              Q        ⁡                  (                      k            ,            f                    )                      where                              R          X                ⁡                  (                      k            ,            f                    )                    =                        1                      n            P                          ⁢                              ∑                          p              =              1                                      n              P                                ⁢                                          ⁢                                                                                    X                  p                                ⁡                                  (                                      k                    ,                    f                                    )                                                                    2                                ,                  ⁢                            R          V                ⁡                  (                      k            ,            f                    )                    =                                                          E              (                              k                ,                f                                                    2                    ≈                                                                V                (                                  k                  ,                  f                                                            2                                          
Comparing this to the expression for the regular Kalman filter gives that                RH(k, f) corresponds to the diagonal elements of P(t)        Q(k, f) corresponds to R1(t) (the variance of the system noise) and may be used to model non-stationarities in the echo path        RV(k, f) corresponds to R2(t) and estimates the variance additive measurement noise        
A fundamental problem with acoustic echo cancellation is to allow re-adaptation in situations where the echo path has changed and retain good echo attenuation in situations with a strong noise component i.e. double-talk conditions.
A common solution to the problem of discriminating double talk from echo path changes is to use a dual-filter structure. This incorporates having two adaptive filters where the filter coefficients are transferred from one filter to the other when either filter is performing significantly better than the other. These schemes pose several problem of determining when either filter is performing significantly better, and also the transfer of filter coefficients may not be suitable when the lengths of the respective filters differs significantly.